import java.util.Scanner;
public class hebing {
public static class Node {
   long value;
   Node next;
   Node(long value) {
        this.value = value;
        this.next = null;
   }
}
    // 合并两个递增有序链表并逆序
public static Node allReverse(Node head1, Node head2) {
    Node dummy = new Node(0); // 创建虚拟头结点，用于简化代码
    Node current = dummy; // 当前结点指针，初始指向虚拟头结点
    // 合并两个链表
    while (head1 != null && head2 != null) {
        if (head1.value < head2.value) {
            current.next = head1; // 如果链表1的当前结点值较小，则将其链接到新链表
            head1 = head1.next; // 将链表1的头结点指针后移
        } else {
            current.next = head2; // 如果链表2的当前结点值较小，则将其链接到新链表
            head2 = head2.next; // 将链表2的头结点指针后移
        }
        current = current.next; // 将当前结点指针后移
    }
    // 将剩余的结点添加到新链表中
    if (head1 != null) {
        current.next = head1; // 如果链表1还有剩余结点，则将它们链接到新链表
    } else if (head2 != null) {
        current.next = head2; // 如果链表2还有剩余结点，则将它们链接到新链表
    }
    return dummy.next; // 返回新链表的头结点
}
    // 逆序链表
public static Node reverseList(Node head) {
    Node prev = null; // 前一个结点指针，初始为null
    Node current = head; // 当前结点指针，初始为链表头结点
    while (current != null) {
        Node next = current.next; // 保存当前结点的下一个结点
        current.next = prev; // 将当前结点的指针域指向前一个结点，实现逆序
        prev = current; // 将前一个结点指针更新为当前结点
        current = next; // 将当前结点指针更新为下一个结点
    }
    return prev; // 返回逆序后的链表头结点
}
// 打印链表
public static void printList(Node head) {
    Node current = head; // 当前结点指针，初始为链表头结点
    while (current != null) {
        System.out.print(current.value + "->"); // 打印当前结点的数据域
        current = current.next; // 将当前结点指针后移
    }
    System.out.println("nullptr"); // 打印链表结束标记
}
public static void main (String[]args){
    Scanner sc = new Scanner(System.in);
    System.out.print("请输入链表1的结点个数:");
    int num1 = sc.nextInt();
    Node head1 = null;
    Node tail1 = null;
    // 创建链表1
    for (int i = 0; i < num1; i++) {
        System.out.print("请输入链表1的第" + (i + 1) + "个结点的值:");
        int value = sc.nextInt();
        Node newNode = new Node(value); // 创建新结点
        if (head1 == null) {
            head1 = newNode; // 如果链表为空，将新结点设为头结点
        } else {
            tail1.next = newNode; // 否则，将新结点链接到尾结点的后面
        }
        tail1 = newNode; // 更新尾结点为新结点
    }
    // 创建链表2
    System.out.print("请输入链表2的结点个数:");
    int num2 = sc.nextInt();
    Node head2 = null;
    Node tail2 = null;
    for (int i = 0; i < num2; i++) {
        System.out.print("请输入链表2的第" + (i + 1) + "个结点的值:");
        int value = sc.nextInt();
        Node newNode = new Node(value);
        if (head2 == null) {
            head2 = newNode;
        } else {
            tail2.next = newNode;
        }
        tail2 = newNode;
    }
    // 打印链表1和链表2
    System.out.print("链表1: ");
    printList(head1);
    System.out.print("链表2: ");
    printList(head2);
    // 合并链表1和链表2为递增有序的链表
    Node all = allReverse(head1, head2);
    // 打印合并后的链表
    System.out.print("合并链表1和链表2: ");
    printList(all);
    // 逆序合并后的链表
    System.out.print("合并链表1和链表2并将其逆序: ");
    Node reversed = reverseList(all);
    printList(reversed);
    }
}




